DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2008.1344

Understanding Maximal Repetitions in Strings

Authors: Maxime Crochemore and Lucian Ilie

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

The cornerstone of any algorithm computing all repetitions in a string of length $n$ in ${mathcal O(n)$ time is the fact that the number of runs (or maximal repetitions) is ${mathcal O(n)$. We give a simple proof of this result. As a consequence of our approach, the stronger result concerning the linearity of the sum of exponents of all runs follows easily.

Cite as

Maxime Crochemore and Lucian Ilie. Understanding Maximal Repetitions in Strings. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 11-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{crochemore_et_al:LIPIcs.STACS.2008.1344,
  author =	{Crochemore, Maxime and Ilie, Lucian},
  title =	{{Understanding Maximal Repetitions in Strings}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{11--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1344},
  URN =		{urn:nbn:de:0030-drops-13442},
  doi =		{10.4230/LIPIcs.STACS.2008.1344},
  annote =	{Keywords: Combinatorics on words, repetitions in strings, runs, maximal repetitions, maximal periodicities, sum of exponents}
}

Search Results

Documents authored by Ilie, Lucian

Understanding Maximal Repetitions in Strings

Abstract

Cite as

Thanks for your feedback!

Could not send message